package com.yangli.leecode.mashib;

/**
 * @Description 递归 N皇后问题
 * @Author liyang
 * @Date 2023/1/11 15:47
 */
public class Recursion {
    public static void main(String[] args){
/*        int[] weights = new int[]{1, 3, 5, 7, 2, 100};
        int[] values = new int[]{2, 4, 9, 3, 5, 10000};
        System.out.println(recursion.choose(weights, values, 6));


        System.out.println(recursion.win(new int[]{50, 70, 100, 1, 4}));*/
        Recursion recursion = new Recursion();
        System.out.println("开始");
        long start = System.nanoTime();
        //System.out.println(start);
        System.out.println(recursion.bitQueen(14));
        System.out.println("优化算法耗时==" + (System.nanoTime() - start) / 1000000);

        long start2 = System.nanoTime();
        //System.out.println(start2);
        System.out.println(recursion.queen(14));
        System.out.println("普通算法耗时==" + (System.nanoTime() - start2) / 1000000);

        System.out.println(recursion.calFeiBoNaQie(8));
        System.out.println(recursion.calFeiBoNaQie2(8));

        System.out.println(recursion.win(new int[]{50, 70, 100, 1, 4}));

    }


    //1对A...26对应Z  从左到右尝试行为
    public int translateNum1(int num){
        if (num < 1) {
            return 0;
        }
        return process(String.valueOf(num).toCharArray(), 0);
    }


    //表示 [...index-1]已经计算好了，现在计算从index位置上出发会有多少终可能
    public int process(char[] num, int index){
        if (index == num.length) {
            return 1;//表明这种方式遍历到结束了，算一种方式
        }
        if (num[index] == '0') {
            return 0;//当前位置为0，以0位开始方式为0
        }
        if (num[index] == '1') {
            int res = process(num, index + 1);
            if (index + 1 < num.length) {
                res += process(num, index + 2);
            }
            return res;
        }
        if (num[index] == '2') {
            int res = process(num, index + 1);
            if (index + 1 < num.length && num[index + 1] >= '0' && num[index + 1] <= '6') {
                res += process(num, index + 2);
            }
            return res;
        }
        //3-9时，只有一种转换继续下一位判断
        return process(num, index + 1);
    }

    //https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
    //0对A...25对应Z
    public int translateNum2(int num){
        if (num < 1) {
            return 0;
        }
        return process2(String.valueOf(num).toCharArray(), 0);
    }

    //表示 [...index-1]已经计算好了，现在计算从index位置上出发会有多少终可能
    public int process2(char[] num, int index){
        if (index == num.length) {
            return 1;//表明这种方式遍历到结束了，算一种方式
        }
        if (num[index] == '1') {
            int res = process2(num, index + 1);
            if (index + 1 < num.length) {
                res += process2(num, index + 2);
            }
            return res;
        }
        if (num[index] == '2') {
            int res = process2(num, index + 1);
            if (index + 1 < num.length && num[index + 1] >= '0' && num[index + 1] <= '5') {
                res += process2(num, index + 2);
            }
            return res;
        }
        //3-9或0时，只有一种转换继续下一位判断
        return process2(num, index + 1);
    }


    public int choose(int[] weights, int[] values, int bag){

        boolean[] choose = new boolean[weights.length];

        return process3(choose, 0, weights, values, bag);
    }

    public int process3(boolean[] choose, int index, int[] weights, int[] values, int bag){
        if (bag <= 0) {
            return 0;
        }
        if (index == choose.length) {
            return allValue(choose, values);
        }
        choose[index] = true;
        int temp = process3(choose, index + 1, weights, values, bag - weights[index]);
        choose[index] = false;
        return Math.max(process3(choose, index + 1, weights, values, bag), temp);
    }

    public int choose2(int[] weights, int[] values, int bag){
        return process4(0, weights, values, bag);
    }

    public int process4(int index, int[] weights, int[] values, int bag){
        if (bag <= 0) {//表示无效
            return -1;
        }
        if (index == weights.length) {//到底最后一位，获取价值为0并停止
            return 0;
        }
        int p1 = process4(index + 1, weights, values, bag);
        int p2 = process4(index + 1, weights, values, bag - weights[index]);//只有两个参数变化
        if (p2 != -1) {
            p2 += values[index];
        }
        return Math.max(p1, p2);
    }

    // 1 2 3 4 7 dp(4,bag-1-2) dp(4,bag-3)减少了这个重复的操作
    public int choose3(int[] weights, int[] values, int bag){
        //表示 到index位置上，还剩bag空间，最大的价值是多少。
        //多申请一个作为最终边界==>默认dp[weights.length][0....bag]都为0,表示到最后的边界位置上，价值肯定都是为0
        int[][] dp = new int[weights.length+1][bag + 1];
        for (int i = weights.length-1; i >=0 ; i--) {//从边界最后获取最大价值为0开始遍历
            for (int j = 0; j < bag; j++) {
                int p1 = dp[i+1][j];
                int p2 = dp[i+1][j-weights[i]];
                if (p2 != -1) {
                    p2 += values[i];
                }
               dp[i][j]= Math.max(p1, p2);
            }
        }
        return dp[0][bag];//最终返回索引从0开始，剩余bag空间的最大价值
    }


    public int allValue(boolean[] choose, int[] values){
        int res = 0;
        for (int i = 0; i < choose.length; i++) {
            if (choose[i]) {
                res += values[i];
            }
        }
        return res;
    }


    public int win(int[] values){
        if (values == null || values.length == 0) {
            return 0;
        }
        return Math.max(f(values, 0, values.length - 1), s(values, 0, values.length - 1));//返回先手或者后手最大的那个
    }

    //先手拿牌
    public int f(int[] values, int l, int r){
        if (l == r) {//先手拿牌，最后一张自己那
            return values[l];
        }
        return Math.max(values[l] + s(values, l + 1, r), values[r] + s(values, l, r - 1)); //在从左或者从右拿牌+对应后手拿牌的最大值

    }

    //后手拿牌
    public int s(int[] values, int l, int r){
        if (l == r) {//后手拿牌，最后一张对手那
            return 0;
        }
        return Math.min(f(values, l + 1, r), f(values, l, r - 1));//对手拿走了左边或者右边的牌，让你选择的肯定是最小的那个
    }


    public int queen(int length){
        if (length < 4) {
            return 0;
        }
        int[] record = new int[length];
        return processQueen(record, 0);
    }

    //record 表示前面row的皇后位置记录，record[0] =0表示 0行皇后在0位置上
    public int processQueen(int[] record, int row){
        if (row == record.length) {
            return 1;
        }
        int res = 0;//在不同位置有几种可能，汇总
        for (int i = 0; i < record.length; i++) {
            if (isValid(record, row, i)) {
                record[row] = i;
                res += processQueen(record, row + 1);
            }
        }
        return res;
    }

    //验证row行column列皇后与之前记录是否冲突
    public boolean isValid(int[] record, int row, int column){
        for (int i = 0; i < row; i++) {//遍历之前的每一行
            //1,列相等为false c==d行不用验证，一行放一个皇后一个个放的 2，是否斜线相等 |a-c|==|b-d|
            //i record[i] row column
            if (record[i] == column || Math.abs(i - row) == Math.abs(record[i] - column)) {
                return false;
            }
        }
        return true;
    }

    //N皇后 常数项优化==>位运算 n^n尝试过程中，快速跳过不能放皇后的位置
    public int bitQueen(int length){
        if (length < 1 || length > 32) {//int最多32位
            return -1;
        }

        int limit = length == 32 ? -1 : (1 << length) - 1;//创建length长度后面为1的数
        return processBitQueen(limit, 0, 0, 0);
    }


    //columnLimit列限制 1已经放过的位置 0未放过的位置  leftLimit左斜线限制  rightLimit右斜线限制
    public int processBitQueen(int limit, int columnLimit, int leftLimit, int rightLimit){
        if (limit == columnLimit) {//表面所有列都选了皇后
            return 1;
        }
        //limit & (~(columnLimit | leftLimit | rightLimit)) 去除限制变量前面的0，并且左限制右移1的去掉
        int pos = limit & (~(columnLimit | leftLimit | rightLimit));
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0) {
            mostRightOne = pos & (~pos + 1);//取pos最右的1
            pos ^= mostRightOne;//pos = pos - mostRightOne
            res += processBitQueen(limit, columnLimit | mostRightOne, (leftLimit | mostRightOne) << 1, (rightLimit | mostRightOne) >>> 1);
        }
        return res;
    }

    public int calFeiBoNaQie(int n){
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return calFeiBoNaQie(n - 1) + calFeiBoNaQie(n - 2);
    }


    public int calFeiBoNaQie2(int n){
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        int[] res = new int[n];
        res[0] = 1;
        res[1] = 1;

        for (int i = 2; i < n; i++) {
            res[i] = res[i - 1] + res[i - 2];
        }
        return res[n - 1];
    }


}
